Field
This disclosure generally relates to computationally solving problems, and may particularly be useful in quantum computing via quantum processors.
Solvers
A solver is a mathematical-based set of instructions executed via hardware circuitry that is designed to solve mathematical problems. Some solvers are general purpose solvers, designed to solve a wide type or class of problems. Other solvers are designed to solve specific types or classes of problems. A non-limiting exemplary set of types or classes of problems includes: linear and non-linear equations, systems of linear equations, non-linear systems, systems of polynomial equations, linear and non-linear optimization problems, systems of ordinary differential equations, satisfiability problems, logic problems, constraint satisfaction problems, shortest path or traveling salesperson problems, minimum spanning tree problems, and search problems.
There are numerous solvers available, most of which are designed to execute on classical computing hardware, that is computing hardware that employs digital processors and/or digital processor-readable nontransitory storage media (e.g., volatile memory, non-volatile memory, disk based media). More recently, solvers designed to execute on non-classical computing hardware are becoming available, for example solvers designed to execute on analog computers, for instance an analog computer including a quantum processor.
Adiabatic Quantum Computation
Adiabatic quantum computation typically involves evolving a system from a known initial Hamiltonian (the Hamiltonian being an operator whose eigenvalues are the allowed energies of the system) to a final Hamiltonian by gradually changing the Hamiltonian. A simple example of an adiabatic evolution is given by:He=(1−s)Hi+sHf  (0a)where Hi is the initial Hamiltonian, Hf is the final Hamiltonian, He is the evolution or instantaneous Hamiltonian, and s is an evolution coefficient which controls the rate of evolution. As the system evolves, the evolution coefficient s goes from 0 to 1 such that at the beginning (i.e., s=0) the evolution Hamiltonian He is equal to the initial Hamiltonian Hi and at the end (i.e., s=1) the evolution Hamiltonian He is equal to the final Hamiltonian Hf. Before the evolution begins, the system is typically initialized in a ground state of the initial Hamiltonian Hi and the goal is to evolve the system in such a way that the system ends up in a ground state of the final Hamiltonian Hf at the end of the evolution. If the evolution is too fast, then the system can transition to a higher energy state, such as the first excited state. Generally, an “adiabatic” evolution is considered to be an evolution that satisfies the adiabatic condition:{dot over (s)}|1|dHe/ds|0|=δg2(s)  (0b)where {dot over (s)} is the time derivative of s, g(s) is the difference in energy between the ground state and first excited state of the system (also referred to herein as the “gap size”) as a function of s, and δ is a coefficient much less than 1. Generally the initial Hamiltonian Hi and the final Hamiltonian Hf do not commute. That is, [Hi, Hf]≠0.
The process of changing the Hamiltonian in adiabatic quantum computing may be referred to as evolution. The rate of change, for example, change of s, is slow enough that the system is always in the instantaneous ground state of the evolution Hamiltonian during the evolution, and transitions at anti-crossings (i.e., when the gap size is smallest) are avoided. The example of a linear evolution schedule is given above. Other evolution schedules are possible including non-linear, parametric, and the like. Further details on adiabatic quantum computing systems, apparatus, and methods are described in, for example, U.S. Pat. Nos. 7,135,701 and 7,418,283.
Quantum Annealing
Quantum annealing is a computation method that may be used to find a low-energy state, typically preferably the ground state, of a system. Similar in concept to classical annealing, the method relies on the underlying principle that natural systems tend towards lower energy states because lower energy states are more stable. However, while classical annealing uses classical thermal fluctuations to guide a system to a low-energy state and ideally its global energy minimum, quantum annealing may use quantum effects, such as quantum tunneling, to reach a global energy minimum more accurately and/or more quickly than classical annealing. In quantum annealing thermal effects and other noise may be present to aid the annealing. However, the final low-energy state may not be the global energy minimum. Adiabatic quantum computation, therefore, may be considered a special case of quantum annealing for which the system, ideally, begins and remains in its ground state throughout an adiabatic evolution. Thus, those of skill in the art will appreciate that quantum annealing systems and methods may generally be implemented on an adiabatic quantum computer. Throughout this specification and the appended claims, any reference to quantum annealing is intended to encompass adiabatic quantum computation unless the context requires otherwise.
Quantum annealing uses quantum mechanics as a source of disorder during the annealing process. The optimization problem is encoded in a Hamiltonian HP, and the algorithm introduces quantum effects by adding a disordering Hamiltonian HD that does not commute with HP. An example case is:HE∝A(t)HD+B(t)HP,  (0c)where A(t) and B(t) are time dependent envelope functions. The Hamiltonian HE may be thought of as an evolution Hamiltonian similar to He described in the context of adiabatic quantum computation above. The delocalization may be removed by removing HD (i.e., reducing A(t)). The delocalization may be added and then removed. Thus, quantum annealing is similar to adiabatic quantum computation in that the system starts with an initial Hamiltonian and evolves through an evolution Hamiltonian to a final “problem” Hamiltonian HP whose ground state encodes a solution to the problem. If the evolution is slow enough, the system will typically settle in the global minimum (i.e., the exact solution), or in a local minimum close in energy to the exact solution. The performance of the computation may be assessed via the residual energy (difference from exact solution using the objective function) versus evolution time. The computation time is the time required to generate a residual energy below some acceptable threshold value. In quantum annealing, HP may encode an optimization problem but the system does not necessarily stay in the ground state at all times. The energy landscape of HP may be crafted so that its global minimum is the answer to the problem to be solved, and low-lying local minima are good approximations.Persistent Current
A superconducting flux qubit (such as a radio frequency superconducting quantum interference device; “rf-SQUID”) may comprise a loop of superconducting material (called a “qubit loop”) that is interrupted by at least one Josephson junction. Since the qubit loop is superconducting, it effectively has no electrical resistance. Thus, electrical current traveling in the qubit loop may experience no dissipation. If an electrical current is coupled into the qubit loop by, for example, a magnetic flux signal, this current may continue to circulate around the qubit loop even when the signal source is removed. The current may persist indefinitely until it is interfered with in some way or until the qubit loop is no longer superconducting (due to, for example, heating the qubit loop above its critical temperature). For the purposes of this specification, the term “persistent current” is used to describe an electrical current circulating in the qubit loop of a superconducting qubit. The sign and magnitude of a persistent current may be influenced by a variety of factors, including but not limited to a flux signal φX coupled directly into the qubit loop and a flux signal φCJJ coupled into a compound Josephson junction that interrupts the qubit loop.
Quantum Processor
A quantum processor may take the form of a superconducting quantum processor. A superconducting quantum processor may include a number of qubits and associated local bias devices. A superconducting quantum processor may also employ couplers to provide tunable communicative connections between qubits. A qubit and a coupler resemble each other but differ in physical parameters. One difference is the parameter, β. Consider an rf-SQUID, superconducting loop interrupted by a Josephson junction, β is the ratio of the inductance of the Josephson junction to the geometrical inductance of the loop. A design with lower values of β, about 1, behaves more like a simple inductive loop, a monostable device. A design with higher values is more dominated by the Josephson junctions, and is more likely to have bistable behavior. The parameter, β is defined a 2πLIC/Φ0. That is, β is proportional to the product of inductance and critical current. One can vary the inductance, for example, a qubit is normally larger than its associated coupler. The larger device has a larger inductance and thus the qubit is often a bistable device and a coupler monostable. Alternatively the critical current can be varied, or the product of the critical current and inductance can be varied. A qubit often will have more devices associated with it. Further details and embodiments of exemplary quantum processors that may be used in conjunction with the present systems and devices are described in, for example, U.S. Pat. Nos. 7,533,068; 8,008,942; 8,195,596; 8,190,548; and 8,421,053.
Many techniques for using quantum annealing to solve computational problems involve finding ways to directly map/embed a representation of a problem to the quantum processor. Generally, a problem is solved by first casting the problem in a contrived formulation (e.g., Ising spin glass, QUBO, etc.) because that particular formulation maps directly to the particular embodiment of the quantum processor being employed. A QUBO with N variables, or spins sε[−1, +1], may be written as a cost function of the form:
                                          E            ⁡                          (              s              )                                =                                                    ∑                i                N                            ⁢                                                h                  i                                ⁢                                  s                  i                                                      +                                          ∑                                  i                  <                  j                                            ⁢                                                J                  ij                                ⁢                                  s                  i                                ⁢                                  s                  j                                                                    ,                            (        1        )            where hi and Jij are dimensionless quantities that specify a desired Ising spin glass instance. Solving this problem involves finding the spin configuration si that minimizes E for the particular set of hi and Jij provided. In some implementations, the allowed range of hiε[−2, 2] and Jijε[−1, 1]. For reasons described later, the hi and Jij are not perfectly represented on the hardware during optimization. These misrepresentations may be defined as control errors:hi→hi±δhi  (2a)Jij→Jij±δJij  (2b)Control errors δh and δJ arise from multiple sources. Some sources of error are time dependent and others are static, but depend on a particular suite of h and J values.Intrinsic/Control Error (ICE)
A quantum processor may implement a time-dependent Hamiltonian of the following form:
                                          ℋ            ⁡                          (              t              )                                                          𝒥              AFM                        ⁡                          (              t              )                                      =                              -                                          ∑                i                            ⁢                                                h                  i                                ⁢                                  σ                  z                                      (                    i                    )                                                                                +                                    ∑                              i                ,                                  j                  >                  i                                                      ⁢                                          J                ij                            ⁢                              σ                z                                  (                  i                  )                                            ⁢                              σ                z                                  (                  j                  )                                                              -                                    ∑              i                        ⁢                                                            Γ                  i                                ⁡                                  (                  t                  )                                            ⁢                              σ                x                                  (                  i                  )                                                                                        (                  3          ⁢          a                )            where Γi(t) is a dimensionless quantity describing the amplitude of the single spin quantum tunneling, and JAFM (t) is an overall energy scale. Equation 3a is the desired or target Hamiltonian. Quantum annealing is realized by guiding the system through a quantum phase transition from a delocalized ground state at t=0, subject to Γi(t=0)hi, Jij, to a localized spin state at t=tf, subject to Γi(tf)hi, Jij. Further details concerning this evolution can be found in Harris et al., Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor, Phys. Rev. B, Vol. 82, Issue 2, 024511, 2010 (“Harris 2010b”). The Hamiltonian given by equation 3a may be implemented on quantum annealing processors using networks of inductively coupled superconducting flux qubits and couplers as described in, for example Harris et al., Compound Josephson-junction coupler for flux qubits with minimal crosstalk, Phys. Rev. B, Vol. 80, Issue 5, 052506, 2009 (“Harris 2009”) and Harris et al., Experimental demonstration of a robust and scalable flux qubit, Phys. Rev. B, Vol. 81, Issue 13, 134510 (“Harris 2010a”). As described in Harris 2010b, the dimensionless parameters hi, Jij, and Γi(t) map onto physical device parameters in the following manner:
                              h          i                =                                                                                            I                  i                  p                                ⁡                                  (                  t                  )                                                                    ⁢                          (                                                                    Φ                    i                    x                                    ⁡                                      (                    t                    )                                                  -                                  Φ                  i                  0                                            )                                                          𝒥              AFM                        ⁡                          (              t              )                                                          (                  3          ⁢          b                )                                          J          ij                =                                            M              ij                        ⁢                                                                          I                  i                  p                                ⁡                                  (                  t                  )                                                                    ⁢                                                                          I                  j                  p                                ⁡                                  (                  t                  )                                                                                                      𝒥              AFM                        ⁡                          (              t              )                                                          (                  3          ⁢          c                )                                                      Γ            i                    ⁡                      (            t            )                          =                                            Δ              i                        ⁡                          (              t              )                                            2            ⁢                                          𝒥                AFM                            ⁡                              (                t                )                                                                        (                  3          ⁢          d                )            where Φix(t) is a time-dependent flux bias applied to a qubit i, Φi0 is the nominally time-independent degeneracy point of qubit i, and Mij is the effective mutual inductance provided by the tunable interqubit coupler between qubits i and j. The time-dependent quantities |Iip(t)| and Δi(t) correspond to the magnitude of the qubit persistent current and tunneling energy, respectively, of qubit i. Averages of these quantities across a processor are indicated by |Iip(t)| and Δi(t). The global energy scale JAFM(t)≡MAFM|Iip(t)| given by the Hamiltonian in equation 3a has been defined in terms of the average qubit persistent current |Iip(t)| and the maximum antiferromagnetic (AFM) mutual inductance MAFM that can be achieved by all couplers across a processor.
Quantum annealing implemented on a quantum processor aims to realize time-independent hi and Jij. Equation 3c naturally yields a time-independent quantity upon substituting the definition of JAFM (t) and assuming that:|Iip(t)|=|jp(t)|=|Iqp(t)|.
In order to expunge the time-dependence from hi in Equation 3b, subject to the assumption that:|Iip(t)=|Iqp(t)|,time-dependent flux bias applied to the i-th qubit Φix(t) of the form:Φix(t)=Miα|Iqp(t)|+Φi0  (3e)should be applied where α|qq(t)| represents an externally supplied bias current that emulates the evolution of the qubit persistent current |Iqp(t)| multiplied by a dimensionless factor α1 and Mi≡hi MAFM/α is the effective mutual inductance between the aforementioned external current bias and the body of qubit i. The logic leading to equation 3e and its implementation in hardware is discussed in detail in Harris 2010b.
Equations 3a-3e link the dimensionless user-specified quantities hi and Jij that define an Ising spin glass instance to the physical properties of qubits and couplers. These hardware elements are subject to practical constraints, both in design and fabrication that ultimately limit the amount of control that the user can exert on the Ising spin glass parameters hi and Jij. The term Intrinsic/Control Error (ICE) defines the resolution to which one hi and Jij can be realized on a quantum processor (i.e., chip). Sources of error can be classified based on whether those sources or error are due to some intrinsic non-ideality of a particular device on a chip or whether they are due to the finite resolution of some control structure. Arguably, the resolution to which Γi can be controlled could have significant bearing on the efficacy of quantum annealing. For the purpose of the present systems and methods, it is assumed that all Γi(t) are identical.
The impact of ICE can be characterized by modifying the definitions of hi and Jij given above to include physical sources of error:
                              h          i                →                                            (                                                                                                            I                      q                      p                                        ⁡                                          (                      t                      )                                                                                        +                                  δ                  ⁢                                                                                                        I                        i                        p                                            ⁡                                              (                        t                        )                                                                                                                            )                        ⁢                          (                                                                    Φ                    i                    x                                    ⁡                                      (                    t                    )                                                  -                                  Φ                  i                  0                                -                                  δ                  ⁢                                                                          ⁢                                      Φ                    i                    0                                                              )                                                          𝒥              AFM                        ⁡                          (              t              )                                                          (                  4          ⁢          a                )                                          J          ij                →                                            (                                                M                  ij                                +                                  δ                  ⁢                                                                          ⁢                                      M                    ij                                                              )                        ⁢                          (                                                                                                            I                      q                      p                                        ⁡                                          (                      t                      )                                                                                        +                                  δ                  ⁢                                                                                                        I                        i                        p                                            ⁡                                              (                        t                        )                                                                                                                            )                        ⁢                          (                                                                                                            I                      q                      p                                        ⁡                                          (                      t                      )                                                                                        +                                  δ                  ⁢                                                                                                        I                        j                        p                                            ⁡                                              (                        t                        )                                                                                                                            )                                                          𝒥              AFM                        ⁡                          (              t              )                                                          (                  4          ⁢          b                )                                                      Φ            i            x                    ⁡                      (            t            )                          →                                            (                                                M                  i                                +                                  δ                  ⁢                                                                          ⁢                                      M                    i                                                              )                        ⁢                                                  ⁢            α            ⁢                                                  ⁢                                                                          I                  q                  p                                ⁡                                  (                  t                  )                                                                            +                      Φ            i            0                                              (                  4          ⁢          c                )            where the assumption is that the global variables MAFM, |Iqp(t)|, and α have been calibrated to high precision. A sparse network of analog control lines that allow for high precision one- and two-qubit operations can be used in order to calibrate these quantities. Thus, δ|Iip(t)|, δ|Ijp(t)|, δΦi0, δMi, and δMij, represent the perturbations that give rise to errors in hi and Jij. Generally, these perturbations are small and so therefore may be neglected in the present systems and methods so that only the errors in hi and Jij that are first order are taken into consideration.
If the deviations in the qubit persistent current δ|Iip(t)|≠0 and δ|Ijp(t)|≠0 and if all other deviations are set to zero, recalling that in the ideal case Mi≡hj*MAFM/α and Mij≡Jij*MAFM, substituting equation 4c into equation 4a and 4b then yields errors in the instance parameters of the following form:
                              δ          ⁢                                          ⁢                      h            i                          =                              h            i                    ⁢                                    δ              ⁢                                                                                    I                    i                    p                                    ⁡                                      (                    t                    )                                                                                                                                                      I                  q                  p                                ⁡                                  (                  t                  )                                                                                                      (                  5          ⁢          a                )                                          δ          ⁢                                          ⁢                      J            ij                          =                                            J              ij                        ⁢                                                                                [                                                                  δ                        ⁢                                                                                                                                      I                              i                              p                                                        ⁡                                                          (                              t                              )                                                                                                                                                                                                                                                          I                            q                            p                                                    ⁡                                                      (                            t                            )                                                                                                                                        ]                                    2                                +                                                      [                                                                  δ                        ⁢                                                                                                                                      I                              j                              p                                                        ⁡                                                          (                              t                              )                                                                                                                                                                                                                                                          I                            q                            p                                                    ⁡                                                      (                            t                            )                                                                                                                                        ]                                    2                                                              →                                    J              ij                        ⁢            2            ⁢                                          δ                ⁢                                                                                              I                      i                      p                                        ⁡                                          (                      t                      )                                                                                                                                                                          I                    q                    p                                    ⁡                                      (                    t                    )                                                                                                                          (                  5          ⁢          b                )            where the assumption in the formula for δJij is the absolute worst-case scenario in which the deviations of the two persistent currents are correlated and equal in magnitude.
Deviations in the mutual inductance δMi≠0, with all others set to zero, only affect hi. Substituting equation 4c into equation 4a yields:
                              δ          ⁢                                          ⁢                      h            i                          =                              δ            ⁢                                                  ⁢                          M              i                                                          M              AFM                        /            α                                              (                  5          ⁢          c                )            Likewise, deviations of the qubit degeneracy point δΦi0, with all others set to zero, also only affect hi. Substituting equation 4c into equation 4a yields a time dependent error:
                              δ          ⁢                                          ⁢                      h            i                          =                                            δ              ⁢                                                          ⁢                              Φ                i                0                                                                    M                AFM                            ⁢                                                                                    I                    q                    p                                    ⁡                                      (                    t                    )                                                                                                .                                    (                  5          ⁢          d                )            Finally, deviations in interqubit coupling mutual inductance δMij, with all others set to zero, only affect Jij as shown below:
                              δ          ⁢                                          ⁢                      J            ij                          =                                            δ              ⁢                                                          ⁢                              M                ij                                                    M              AFM                                .                                    (                  5          ⁢          e                )            It is worth noting that deviations in the qubit persistent current δ|Iip(t)|≠0 and δ|Ijp(t)|≠0 lead to relative errors in the problem instance settings, as given by equations 5a and 5b. In contrast, deviations in mutual inductances and flux offsets lead to absolute errors. One convention defines the allowed range of problem instance specifications to be −1≦hi, Jij≦1. For relative errors, an upper bound on an absolute error is realized if |hi|=|Jij|=1.
Equations 5a to 5e produce absolute errors (or upper bounds on absolute errors) as a function of perturbations in qubit persistent current δ|Iip(t)|, qubit degeneracy point δΦi0, mutual inductance δMi, and interqubit coupling δMij. Identifying the physical mechanisms that give rise to these four quantities and studying worst-case scenarios under which those mechanisms give rise to ICE may help reduce such errors.
Performance Metrics
As in common with optimization heuristics, whether quantum or classical, performance can be characterized by a trade-off between computation time and solution quality. More time generally yields better solutions. A performance metric can be used to quantify performance of a method.
One performance metric is STS (samples to solution) and is the expected number of samples to reach an optimal solution. It can also be expressed as TTS (time to solution) where the number of samples is multiplied by the time to generate each sample.
Another performance metric is STE (samples to epsilon) and is the expected number of samples to reach a solution energy within a distance ε of optimal. TTE (time to epsilon) is obtained by multiplying sample time by the samples to epsilon.
A third metric is TTT (time to target). When quantum annealers are used to solve NP-hard optimization problems, for example, computation of the optimal cost is not always feasible. An advantage of TTT is that it does not require knowledge of optimal solutions. In one approach, the convergence of minimum sample energies is compared for two solvers.